package com.lw.leetcode.sort.b;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;

/**
 * Created with IntelliJ IDEA.
 * 497. 非重叠矩形中的随机点
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/9 9:11
 */
public class Solution {

    public static void main(String[] args) {
        int[][] arr = {{82918473, -57180867, 82918476, -57180863}, {83793579, 18088559, 83793580, 18088560}, {66574245, 26243152, 66574246, 26243153}, {72983930, 11921716, 72983934, 11921720}};
        Solution test = new Solution(arr);
        System.out.println(test.map);
        for (int i = 0; i < 100000; i++) {
            check(arr, test.pick());
        }
        System.out.println(m);
        System.out.println(m2);
    }

    private static Map<Integer, Integer> m = new HashMap<>();
    private static Map<Integer, Integer> m2 = new HashMap<>();

    private static void check(int[][] arr, int[] items) {
        int a = items[0];
        int b = items[1];
        int length = arr.length;
        for (int i = 0; i < length; i++) {
            int[] ints = arr[i];
            if (a >= ints[0] && a <= ints[2] && b >= ints[1] && b <= ints[3]) {
//                System.out.println(i + "  " + (a - ints[0]) + "  " + (b - ints[1]));
                m.merge(i, 1, (r, t) -> r + t);
                return;
            }
        }
        System.out.println(Arrays.toString(items));
    }

    private TreeMap<Long, Integer> map = new TreeMap<>();
    private int[][] rects;
    private long sum;
    private long[] counts;

    public Solution(int[][] rects) {
        int length = rects.length;
        this.rects = rects;
        this.counts = new long[length];
        for (int i = 0; i < length; i++) {
            int[] rect = rects[i];
            long a = (long) rect[2] - rect[0] + 1L;
            long b = (long) rect[3] - rect[1] + 1L;
            counts[i] = a * b;
            sum += counts[i];
            map.put(sum, i);
        }
    }

    public int[] pick() {
        long v = (long) (Math.random() * sum) + 1;
        Map.Entry<Long, Integer> en = map.ceilingEntry(v);
        int i = en.getValue();
        int[] rect = rects[i];
        long a = (long) rect[2] - rect[0] + 1L;
        v = (long) (Math.random() * counts[i]);
        return new int[]{(int) (rect[0] + v % a), (int) (rect[1] + v / a)};
    }

}
